package datastructure.tree;

/**
 * @author XY
 * @version 1.0
 * @date 2022/1/7 9:21
 * @Description 给定一个二叉树，检查它是否是镜像对称的。未完成
 */
public class Leet101 {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    class Solution {
        public boolean isSymmetric(TreeNode root) {
            return check(root, root);
        }

        /**
         * 我们可以实现这样一个递归函数，通过「同步移动」两个指针的方法来遍历这棵树，
         * p 指针和 q 指针一开始都指向这棵树的根，随后 p 右移时，q 左移，p 左移时，q 右移。
         * 每次检查当前 p 和 q 节点的值是否相等，如果相等再判断左右子树是否对称。
         */
        private boolean check(TreeNode p, TreeNode q) {
            if(p==null&&q==null){
                return true;
            }
            if(p==null||q==null){
                return false;
            }
            if(p.val!=q.val){
                return false;
            }
            return check(p.left,q.right)&&check(p.right,q.left);
        }
    }
}
